The present invention relates generally to data encoding and decoding techniques and, more specifically, to a method for encoding and decoding images to achieve lossless data compression.
Various display-based electronic devices require acquisition, storage, retrieval, and transmission of images. An image is stored in memory as a spatially mapped array of bits, referred to as a bitmap. Typically, images, in the form of bitmaps, require a large amount of memory space for storage and also high bandwidths for transfer, both internally, within an electronic device, and externally, between two or more electronic devices. For example, a 1024×1024 pixel gray scale image requires 1,048,576 bits of memory space and can take several minutes to be retrieved from the memory and transmitted to a display screen in the electronic device. Accordingly, it is desirable to reduce the amount of data required for representing the image to facilitate reduction in memory space required to store the image and reduction in bandwidth required for internal and external transfer of the image.
Due to resource limitations of embedded devices, the demand for techniques to enable data transmission at low bit-rates and reduce memory space requirements is high. A large variety of image compression techniques have been developed with the intent of eliminating redundancy in image data. Examples of image compression techniques include run length encoding (RLE), Huffman coding, Lempel-ziv-welch (LZW), and JPEG.
RLE is a lossless compression technique. In RLE, a “run” of pixels, i.e., a series of repetitive pixels of the same value within a row is encoded in a shorter code having two bytes. One byte, known as “run count”, represents the length of the run and the other byte, known as “run value”, represents the pixel value being repeated. For example, a character run of 10 “B” characters (“BBBBBBBBBB”) is stored as “10B” in the memory, where 10 represents the “run count” and “B” represents the “run value”. Hence, instead of storing each pixel value individually, only the “run count” and the “run value” are stored and thus, the memory space and bandwidth requirements are considerably reduced.
However, use of RLE for image compression also poses several challenges. RLE takes into account only horizontal redundancy of the image data, which results in comparatively lower compression ratios. Further, in the encoded image, it is difficult to distinguish between a byte containing the “run value” and the one containing the “run count”. In accordance with one solution, at least one bit in each byte is devoted to indicating whether the byte contains the “run value” or the “run count”. However, this methodology is useful only if the image is limited to 128 colors. In accordance with another solution, one bit is devoted to each byte to indicate the presence of the “run count” or the “run value”. These extra bits are written as a compact array at the start of the encoded image. For example, the compact array corresponding to the encoded image 6, 4, 18, 9, 3, 4, 5, 7, 6 . . . , where 6, 18, and 7 correspond to the “run count”, is written as 101000010 . . . at the start of the encoded image. However, the size of the compact array is one-eighth the size of the encoded image as it contains one bit for each byte of the encoded image and thus, increases the overall size and consequently decreases the compression ratios and the throughput capability of the technique.
It would be desirable to have an encoding technique that has higher compression ratios, can identify horizontal as well as vertical redundancy in the image data, does not alter the quality of the image, and can be implemented with minimal hardware and software requirements.